package com.atguigu.algorithm.search;

import java.util.ArrayList;

/**
 * 二分查找
 * 二分查找中中间值的计算：
 * 这是一个经典的话题，如何计算二分查找中的中值？大家一般给出了两种计算方法：
 * 算法一： mid = (low + high) / 2
 * 算法二： mid = low + (high – low)/2
 * 乍看起来，算法一简洁，算法二提取之后，跟算法一没有什么区别。
 * 但是实际上，区别是存在的。算法一的做法，在极端情况下，(low + high)存在着溢出的风险，进而得到错误的mid结果，导致程序错误。
 * 而算法二能够保证计算出来的mid，一定大于low，小于high，不存在溢出的问题。
 *
 * @author xr-8
 * @create 2021-03-03 13:34
 */
public class BinarySearch {

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        binarySearch(arr, 1);
        binarySearch2(arr, 0, arr.length - 1, 103);
        int[] arr3 = {1, 8, 10, 89, 1000, 1000, 1234};
        System.out.println(binarySearch3(arr3, 0, arr.length - 1, 1000));
    }

    /**
     * 循环实现二分查找
     *
     * @param arr
     * @param num
     * @return
     */
    public static int binarySearch(int[] arr, int num) {
        int min = 0;
        int max = arr.length - 1;
        int mid = 0;
        int index = -1;

        if (num < arr[min] || num > arr[max] || min > max) {
            System.out.println("没有找到！" + index);
            return index;
        }

        while (min <= max) {
            mid = min + (max - min) / 2;
            if (num > arr[mid]) {
                min = mid + 1;
            } else if (num < arr[mid]) {
                max = mid - 1;
            } else {
                index = mid;
                System.out.println("找到了！脚标：" + index);
                break;
            }
        }
        if (index == -1) {
            System.out.println("没有找到！" + index);
        }
        return index;
    }

    /**
     * 递归实现二分查找
     *
     * @param arr
     * @param min
     * @param max
     * @param num
     * @return
     */
    public static int binarySearch2(int[] arr, int min, int max, int num) {
        int index = -1;
        if (num < arr[min] || num > arr[max] || min > max) {
            System.out.println("没有找到·！" + index);
            return index;
        }

        int mid = min + (max - min) / 2;
        if (num < arr[mid]) {
            binarySearch2(arr, min, mid - 1, num);
        } else if (num > arr[mid]) {
            binarySearch2(arr, mid + 1, max, num);
        } else {
            index = mid;
            System.out.println("找到了！脚标：" + index);
        }
        return index;
    }

    /**
     * 课后思考题： {1,8, 10, 89, 1000, 1000, 1234} 当一个有序数组中，
     * 有多个相同的数值时，如何将所有的数值都查找到，比如这里的 1000
     * <p>
     * 思路分析
     * 1. 在找到mid 索引值，不要马上返回
     * 2. 向mid 索引值的左边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 3. 向mid 索引值的右边扫描，将所有满足 1000， 的元素的下标，加入到集合ArrayList
     * 4. 将Arraylist返回
     */
    public static ArrayList binarySearch3(int[] arr, int min, int max, int num) {
        // 当 left > right 时，说明递归整个数组，但是没有找到
        if (min > max) {
            return new ArrayList<Integer>();
        }

        int mid = min + (max - min) / 2;
        if (num < arr[mid]) {
            return binarySearch3(arr, min, mid - 1, num);
        } else if (num > arr[mid]) {
            return binarySearch3(arr, mid + 1, max, num);
        } else {
            ArrayList<Integer> resIndexlist = new ArrayList<Integer>();
            int left = mid - 1;
            while (true) {
                if (arr[left] == num) {
                    resIndexlist.add(left);
                }
                left--;
                if (left < 0 || arr[left] != num) {
                    break;
                }
            }
            int right = mid;
            while (true) {
                if (arr[right] == num) {
                    resIndexlist.add(right);
                }
                right++;
                if (right < 0 || arr[right] != num) {
                    break;
                }
            }
            return resIndexlist;
        }
    }

}
